import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;
import java.util.concurrent.Callable;

public class BinaryTree {

    public class TreeNode
    {
        public char val;//数据域
        TreeNode left;//左孩子
        TreeNode right;//you孩子

        public TreeNode(char val) {
            this.val = val;
        }

    }
    public TreeNode root;//二叉树的根节点

    //创建二叉树
    public TreeNode createTree()
    {
        TreeNode A=new TreeNode('A');
        TreeNode B=new TreeNode('B');
        TreeNode C=new TreeNode('C');
        TreeNode D=new TreeNode('D');
        TreeNode E=new TreeNode('E');
        TreeNode F=new TreeNode('F');
        TreeNode G=new TreeNode('G');
        TreeNode H=new TreeNode('H');

        A.left=B;
        A.right=C;
        B.left=D;
        B.right=E;
        C.left=F;
        C.right=G;
        E.right=H;

        this.root=A;
        return root;
    }
    // 前序遍历
    public void preOrder(TreeNode root)
    {
        if(root==null)
        {
            return;
        }
        System.out.print(root.val+" ");
        preOrder(root.left);
        preOrder(root.right);
    }
    // 中序遍历
    public void inOrder(TreeNode root)
    {
        if(root==null)
        {
            return;
        }

        inOrder(root.left);
        System.out.print(root.val+" ");
        inOrder(root.right);
    }
    // 后序遍历
    public void postOrder(TreeNode root)
    {
        if(root==null)
        {
            return;
        }

        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val+" ");
    }

    // 获取树中节点的个数
    int size(TreeNode root)
    {
        if(root==null)
        {
            return 0;
        }
        int leftsize=size(root.left);
        int rightsize=size(root.right);
        return leftsize+rightsize+1;
    }
    // 获取叶子节点的个数
    int usesize=0;
    void size2(TreeNode root)
    {
        if(root==null)
        {
            return ;
        }
        usesize++;
      size2(root.left);
      size2(root.right);

    }
    // 子问题思路-求叶子结点个
    int getLeafNodeCount(TreeNode root)
    {
        if(root==null)
        {
            return 0;
        }
        if(root.left==null&&root.right==null)
        {
            return 1;
        }
        int leftsize=getLeafNodeCount(root.left);
        int rightsize=getLeafNodeCount(root.right);
        return leftsize+rightsize;
    }

 //获取第K层节点的个数
    int getKLevelNodeCount(TreeNode root,int k)
    {
        if(root == null) {
            return 0;
        }
        if(k == 1) {
            return 1;
        }
        int leftSize = getKLevelNodeCount(root.left,k-1);
        int rightSize = getKLevelNodeCount(root.right,k-1);
        return leftSize+rightSize;
    }
    // 获取二叉树的高度
    public int getHeight(TreeNode root) {
        if(root == null) {
            return 0;
        }
        int leftHigh=getHeight(root.left);
        int rightHigh=getHeight(root.right);
        return (leftHigh>rightHigh)?(leftHigh+1):(rightHigh+1);
    }
    // 检测值为value的元素是否存在
    TreeNode find(TreeNode root, int val)
    {
        if(root==null)
        {
            return null;
        }
        if(root.val==val) {
            return root;
        }
        TreeNode leftTree=find(root.left,val);
        if(leftTree!=null)
        {
            return leftTree;
        }
        TreeNode rightTree=find(root.right,val);
        if(rightTree!=null)
        {
            return rightTree;
        }

        return null;
    }
    //层序遍历
    public void levelOrder(TreeNode root) {
        if(root == null) {
            return;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            System.out.print(cur.val+" ");
            if(cur.left != null) {
                queue.offer(cur.left);
            }
            if(cur.right != null) {
                queue.offer(cur.right);
            }
        }
    }
    // 判断一棵树是不是完全二叉树
    boolean isCompleteTree(TreeNode root){
        if(root == null) {
            return true;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            if(cur != null) {
                queue.offer(cur.left);
                queue.offer(cur.right);
            }else {
                break;
            }
        }
        while (!queue.isEmpty()) {
            TreeNode tmp = queue.poll();
            if(tmp != null) {
                return false;
            }
        }
        return true;
    }

    //二叉树前序遍历（非递归）
    public void preOrder1(TreeNode root)
    {
        if(root==null)
        {
            return;
        }
        TreeNode cur =root;
        Deque<TreeNode> stack=new ArrayDeque<>();
        while(cur!=null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                System.out.println(cur.val + " ");
                cur = cur.left;
            }
            TreeNode top = stack.pop();
            cur = top.right;
        }
    }

    // 中序遍历
    void inOrder1(TreeNode root)
    {
        if(root==null)
        {
            return;
        }
        TreeNode cur =root;
        Deque<TreeNode> stack=new ArrayDeque<>();
        while(cur!=null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);

                cur = cur.left;
            }
            TreeNode top = stack.pop();
            System.out.println(top.val + " ");
            cur = top.right;
        }
    }
    // 后序遍历
    void postOrder1(TreeNode root)
    {
        if(root==null)
        {
            return;
        }
        TreeNode cur =root;
        TreeNode prev=null;
        Deque<TreeNode> stack=new ArrayDeque<>();
        while(cur!=null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode top = stack.peek();
            if(cur.right==null || top.right==prev)
            {
                System.out.println(top.val + " ");
                stack.pop();
                prev=top;
            }
            else
            {
                cur = top.right;
            }


        }
    }


}

